package cn.ecut.dzy.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * @program: datastructure
 * @description:给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，
 * 使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
 * <p>
 * 注意：答案中不可以包含重复的三元组。
 * @author: DingZhenYun
 * @create: 2021-10-31 17:55
 **/

public class ThreeSum {
    // 方法一：暴力法
    public List<List<Integer>> threeSum1(int[] nums) {
        // 定义结果列表
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                for (int k = i + 2; k < n; k++) {
                    if ((nums[i] + nums[j] + nums[k]) == 0) {
                        result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    }
                }
            }
        }
        return result;
    }

    // 方法二：使用哈希表保存结果
    public List<List<Integer>> threeSum2(int[] nums) {
        int n = nums.length;
        List<List<Integer>> result = new ArrayList<>();
        // 定义一个hash map
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        // 遍历数组，寻找每个数对应的那个数
        for (int i = 0; i < n; i++) {
            int thatNum = 0 - nums[i];
            if (map.containsKey(thatNum)) {
                // 如果已经存在thatNum，就找到了一组解
                ArrayList<Integer> tempList = new ArrayList<>(map.get(thatNum));
                tempList.add(nums[i]);
                result.add(tempList);
            }

            // 把当前数对应的两数组合都保存到map里
            for (int j = 0; j < i; j++) {
                // 以两数之和作为key
                int newKey = nums[i] + nums[j];
                // 如果key不存在，就直接添加进去
                if (!map.containsKey(newKey)) {
                    ArrayList<Integer> tempList = new ArrayList<>();
                    tempList.add(nums[i]);
                    tempList.add(nums[j]);
                    map.put(newKey, tempList);
                }
            }
        }
        return result;
    }

    // 方法三：双指针法
//    特判，对于数组长度 nn，如果数组为 nullnull 或者数组长度小于 33，返回 [][]。
//    对数组进行排序。
//    遍历排序后数组：
//    若 nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 00，直接返回结果。
//    对于重复元素：跳过，避免出现重复解
//    令左指针 L=i+1L=i+1，右指针 R=n-1R=n−1，当 L<RL<R 时，执行循环：
//    当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,R 移到下一位置，寻找新的解
//    若和大于 00，说明 nums[R]nums[R] 太大，RR 左移
//    若和小于 00，说明 nums[L]nums[L] 太小，LL 右移


    public List<List<Integer>> threeSum3(int[] nums) {
        int n = nums.length;

        List<List<Integer>> result = new ArrayList<>();

        // 0. 先对数组排序
        Arrays.sort(nums);
        // 1. 遍历每一个元素，作为当前三元组中最小的那个（最矮个做核心）
        for (int i = 0; i < n; i++) {
            // 1.1 如果当前数已经大于0，直接退出循环
            if (nums[i] > 0) {
                break;
            }
            // 1.2 如果当前数据已经出现过，直接跳过
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            // 1.3 常规情况，以当前数做最小数，定义左右指针
            int lp = i + 1;
            int rp = n - 1;
            // 只要左右指针不重叠，就继续移动指针
            while (lp < rp) {
                int sum = nums[i] + nums[rp] + nums[lp];
                if (sum == 0) {
                    //等于0，就是找到了一组解
                    result.add(Arrays.asList(nums[i], nums[lp], nums[rp]));
                    lp++;
                    rp--;
                    // 如果移动之后的元素相同，直接跳过
                    // 如果移动之后的元素相同，直接跳过
                    while (lp < rp && nums[lp] == nums[lp - 1])
                        lp++;
                    while (lp < rp && nums[rp] == nums[rp + 1])
                        rp--;
                } else if (sum > 0) {
                    //大于0，较大的数减小，右指针左移
                    rp--;
                } else if (sum < 0) {
                    //小于0，较小的数增大，左指针右移
                    lp++;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] input = {-1, 0, 1, 2, -1, -4};

        ThreeSum threeSum = new ThreeSum();
        System.out.println(threeSum.threeSum1(input));
        System.out.println(threeSum.threeSum2(input));
        System.out.println(threeSum.threeSum3(input));

    }
}

